// 93.复原IP地址
package Leetcode_Second_Brush;

import java.util.ArrayList;
import java.util.List;

public class Solution093 {
    List<String> result = new ArrayList<>();
    List<String> ipAddress = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        backTrace(s, 0, 0);
        return result;
    }

    private void backTrace(String s, int index, int count) {
        // 如果已经遍历完成且分为四段
        if (count == 4 && index == s.length()) {
            result.add(String.join(".", ipAddress));
            return;
        }

        for (int i = index; i < s.length() && i < index + 3; i++) {
            if (s.charAt(index) == '0' && i > index) // 如果 i~index 中存在前置0则直接返回
                return;
            // i~index 中没有前置0，判断是否处于0~255
            int val = Integer.parseInt(s.substring(index, i + 1));
            if (0 <= val && val <= 255) {
                ipAddress.add(String.valueOf(val));
                backTrace(s, i + 1, count + 1);
                ipAddress.remove(ipAddress.size() - 1);
            }
        }
    }
}
